import java.util.*;

public class Leetcode {
}

//leetcode:662:二叉树的最大宽度
class Solution1 {
    public int widthOfBinaryTree(TreeNode root) {
        //将树的结点进行编号存入数组中
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();
        //将根节点存入
        q.add(new Pair<TreeNode,Integer>(root,1));
        int ret = 0;
        //如果此时数组不为空
        while (!q.isEmpty()) {
            //得到此时数组的第一个结点
            Pair<TreeNode,Integer> t1 = q.get(0);
            ///得到此时数组的最后一个结点
            Pair<TreeNode,Integer> t2 = q.get(q.size()-1);
            //得到每一层的宽度的最大值
            ret = Math.max(ret,t2.getValue() - t1.getValue() + 1);

            //创建一个临时数组
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            //遍历原数组，并取出每个值
            for (Pair<TreeNode,Integer> t : q ) {
                //得到每个值对应的结点和编号
                TreeNode node = t.getKey();
                int index = t.getValue();
                //如果此时结点左节点存在，将结点放入数组中并进行编号（如果是左孩子且根节点从1开始，那么编号就是父节点的2倍）
                if(node.left != null) tmp.add(new Pair<TreeNode,Integer>(node.left,index * 2));
                //如果此时结点右节点存在，将结点放入数组中并进行编号（如果是右孩子且根节点从1开始，那么编号就是父节点的2倍+1）
                if(node.right != null) tmp.add(new Pair<TreeNode,Integer>(node.right,index * 2 + 1));
            }
            //将原数组的值更新成临时数组的值
            q = tmp;
        }
        return ret;
    }
}

//leetcode:515:在每个树行中找最大值
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            int n = q.size();
            int tmp = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                TreeNode node = q.poll();
                tmp = Math.max(tmp,node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            ret.add(tmp);
        }
        return ret;
    }
}